public class MinPathSum {
    public int minPathSum(int[][] grid) {
        int len1 = grid.length, len2 = grid[0].length;
        int[][] dp = new int[len1+1][len2+1];
        int INF = 0x3f3f3f3f;
        for (int j = 0; j <= len2; j++) {
            dp[0][j] = INF;
        }
        for (int i = 1; i <= len1; i++) {
            dp[i][0] = INF;
        }
        dp[0][1] = 0;
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i-1][j-1];
            }
        }
        return dp[len1][len2];
    }

    public static void main(String[] args) {
        MinPathSum minPathSum = new MinPathSum();
        System.out.println(minPathSum.minPathSum(new int[][]{{1,3,1}, {1,5,1},{4,2,1}}));
    }
}
